This invention relates to content-addressable memories (CAM), and more particularly to data-move operations in a CAM.
Content-addressable memories (CAM) have been widely used for address translation caches known as translation-lookaside buffers (TLB""s). CAM""s are also being used to perform more general logic operations, especially when parallel operations are performed on a large data set. For example, image processing may manipulate a large array of pixels that make up an image. Operations may be performed on many pixels in parallel, such as reversing a background color for a special effect or removing a red color from foreground objects that represent human eyes (red-eye reduction).
Using a CAM array to perform such operations rather than sequential logic or a microprocessor allows many operations to be performed at the same time on different data items such as pixels in an image, or weather data readings on a map. Such CAM-based logical units are sometimes known as Associative Array Processors.
An associative processing architecture employs a CAM to perform parallel operations on a particular data set. For example, pixels representing a landscape image could be loaded into the CAM array. The data stored in the CAM can be searched for pixels having a numeric value representing blue colors, either a single color or a range of values representing a range of blue colors. The locations of these blue pixels is recorded and used to select them for following operations, such as changing the blue color to a darker blue, or even reversing the blue color to an orange color.
Data Movement in a CAM
When a complex series of operations needs to be performed on data, it may be more efficient to move the selected pixels to a new location in the CAM. In the new location, data can be repeatedly operated on without altering the non-selected data. For example, pixels in foreground objects in the image may be extracted and operated upon before being merged back into the image. The extracted pixels could be further searched for sub-objects, such as searching for eye shapes in face objects that were moved from the background image. The eye pixels could then be altered for red-eye reduction before the eye and face pixels are moved back into the full image data in another part of the CAM array.
Being able to move data blocks within the CAM array is thus useful for more efficient coding of associative-processing operations. The CAM array may have several columns or banks of data, each of which can be separately searched for matching data values. The programmer may load the original data into a first bank, perform a search for matching data values, then move these matching data values to a second bank. Data-manipulating operations can then be performed on the matching data in the second bank without altering the data in the first bank. Operating on such isolated data can be more efficient, especially when many operations and/or searches are performed in a complex processing sequence.
FIG. 1 shows a data-block move in a CAM array. The CAM array has three multi-bit columns or banks of CAM cells. Data can be accessed (written into or read from) first CAM bank 12 through read-write register 14 at the bottom of the array, while second CAM bank 22 is accessed through read-write register 24, and third CAM bank 32 is accessed through read-write register 34.
CAM memory cells each store a bit of data, often using a static latch such as a cross-coupled pair of inverters. Pass transistors can connect the CAM-cell latch to a pair of bit lines to allow reading and writing of the CAM cell much like a static random-access memory (SRAM) cell. Each row of each CAM bank can have many bits, such as 64 bits stored in 64 CAM cells for each row of CAM bank 12. Read-write register 14 can receive 64 data bits from read-write bus 16, and drive 64 pairs or bits lines to CAM bank 12. A row decoder (not shown) can select one or more of the rows in CAM bank 12 for reading or writing.
A row of data (a data word) can be moved from first CAM bank 12 to second CAM bank 22 using the bottom port. For example, a selected row of first CAM bank 12 is read, and the data stored in read-write register 14. Then the data from read-write register 14 is driven to read-write bus 16 and written to read-write register 24. Finally the data from read-write register 24 is driven onto the bit lines of second CAM bank 22 and written into a row of CAM cells selected by a row decoder (not shown) for second CAM bank 22.
This process can then be repeated for all data in first CAM bank 12 that is to be moved to second CAM bank 22. When many rows of data need to be moved, the move operation can be quite lengthy, reducing performance.
A CAM cell also has a compare port. For example, the data in each CAM cell can drive a gate or a drain of a compare transistor that connects to a compare bit line. Often a pair of compare bits lines are used with a pair of compare transistors in each CAM cell. The outputs of the compare transistors are connected to a row output line known as a row-match line or match line. Compare data from a compare register is driven to the compare bit lines, turning on one of the compare transistors and turning off the other compare transistor in each CAM cell, for all rows of CAM cells in the bank. The data in each CAM cell is basically exclusive OR""ed (or exclusive NOR""ed) with the compare data on the compare bit lines. When the compare data mis-matches the data stored in the CAM cell, the match line is driven to an un-match state. Any data in the row that does not match causes the row""s match line to be driven inactive. When all data in a row matches, the match line is left in the match state.
Data is driven from compare register 10 at the top of first CAM bank 12 to the compare bit line in first CAM bank 12. Rows that store data that match the compare-line data have their match lines activated, while rows with at least one mis-matching CAM cell have their match lines driven inactive. The match lines for all rows can be stored in results register 26. One result bit can be stored for each of CAM banks 12, 22, 32 in results register 26.
Some CAM cells allow a write from the compare port as well as a compare-read. A row-write-enable signal can drive a transistor gate that connects an internal cell node to a ground. This cell node is known as a virtual-ground. When the virtual-ground node is driven to ground when a virtual-ground transistor is activated by the row-write-enable signal, the data from the compare bit lines is written to the data latch in the CAM cell.
Rather than move one data word at a time over read-write bus 16, a block of data can be moved using results register 26. A first data value is loaded from compare-input bus 18 to compare register 10, and compared to data values in first CAM bank 12. The match results are stored in results register 26. Results register 26 holds a xe2x80x9c1xe2x80x9d for a row when the data in compare register 10 matches the data word in the CAM cells for that row. The match result is fed back to the CAM array as the row-write-enable that drives the virtual ground node to ground, writing the compare bits lines back to the CAM cell latch.
These match values can then be used to write the compare data to the same rows in a different bank. The same compare data is written to compare register 20 for second CAM bank 22. Then the match bits from results register 26 are used as write-enables to enable writing from compare register 20 to selected rows of second CAM bank 22. The selected rows are the same rows that had matches from first CAM bank 12. Thus the data is effectively copied over from the matching rows of first CAM bank 12 to the same rows of second CAM bank 22. Compare register 10 can then be written with zeros and the stored match bits from results register 26 used to over-write the data words in first CAM bank 12 that were moved. This process can be repeated for all other possible data values of data in the block to be moved. When repeated data values are common, this second method may be faster than using read-write registers 14, 24.
Either method of moving a block of data from one CAM bank to another CAM bank is lengthy and relatively slow. The programmer has to create routines to read and write each row, or to load compare registers, compare and store match results, write to another bank, and clear the old data.
What is desired is a block-move operation for a CAM array. A bank-swap operation is desired that can move the data values of one CAM bank to another CAM bank. A fast swap operation is desirable that can swap CAM banks in a single step. CAM-bank-swapping hardware to facilitate such a bank-swap is desirable for an associative processor that uses a CAM to perform logic operations on data stored in a CAM.